package com.myc.subjects.string;

import java.util.*;

/**
 * LeetCode题号：316
 *
 * 去除重复字母
 *
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 * 示例 1：
 * 输入：s = "bcabc"
 * 输出："abc"
 *
 * 示例 2：
 * 输入：s = "cbacdcbc"
 * 输出："acdb"
 *
 * 提示：
 * 1 <= s.length <= 104
 * s 由小写英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicate-letters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Quchuchongfuzimu {

    public static void main(String[] args) {
        String s = "ccaabb";
        Quchuchongfuzimu quchuchongfuzimu = new Quchuchongfuzimu();
        System.out.println(quchuchongfuzimu.removeDuplicateLetters3(s));
    }

    /**
     * 方法一：暴力递归法（贪心策略）
     * 时间复杂度：O(n^3) 注意：递归是常数时间复杂度，因为字母最多只有26个
     * 去除重复字母，同时还要保证字母序最小，我们则需要现先选取一个基准字符（position位置），
     * 然后遍历这个字符串，找到相对比基准字符更小的字符（i位置），判断他前面的每个字符（j位置）是不是在他后面（k位置）都出现过，
     * 如果是，则将基准字符移动至i位置，i++循环调用，直到找到第一个不能去掉的position为止；
     * 如果不是（也就是找到了不能去掉的position位置的字符），将字符串截取到position，并去掉position后面的与position处字符一样的字符，再递归调用
     */
    public String removeDuplicateLetters1(String s) {
        //处理特殊情况
        if(s.length() == 0) return "";
        //定义基准位置
        int position = 0;
        //循环遍历寻找比基准位置字符更小的字符
        for(int i = 0; i < s.length(); i++){

            if(s.charAt(i) < s.charAt(position)){
                boolean isReplaceable = true;//定义position位置字符是否可被i位置字符替换的标志

                for(int j = position; j < i; j++){
                    boolean isDuplicated = false;//判断i位置字符前面的第j位置字符是否在i位置后面出现的标志
                    for(int k= i + 1; k < s.length(); k++){
                        if(s.charAt(j) == s.charAt(k)){
                            isDuplicated = true;
                            break;//出现跳出循环
                        }
                    }
                    if(!isDuplicated) {
                        isReplaceable = false;//只要出现一个不重复的情况，position位置就不可被替换
                        break;
                    }
                }
                //前面的字符在后面都出现了，移动基准位置position到i的位置，再向后寻找下一个可能的position
                if(isReplaceable) position = i;
            }
        }

        //找到第一个不能移动的position之后，将字符串截取到position，并去掉position后面的与position处字符一样的字符，再递归调用
        return s.charAt(position) + removeDuplicateLetters1(s.substring(position + 1).replaceAll(s.charAt(position) + "",""));

    }

    /**
     * 方法二：贪心策略改进（空间换时间）
     * 时间复杂度：O(n)
     * 在方法一种我们寻找重复字母时，是通过遍历i位置前面和后面的字符来判断前后是否出现重复字符，
     * 现在我们可以将26个字母在字符串中出现的次数，保存到一个count[]数组中，通过遍历使得count数组中对应位置的计数值减1，
     * 在找到第一个减到0的数据时，如果他比position位置的字母小，则他就是最左侧字符，否则position位置就是最左侧字符
     * 再递归调用，就可找出去重字符串
     */
    public String removeDuplicateLetters2(String s) {
        //处理特殊情况
        if(s.length() == 0) return "";
        //定义基准位置
        int position = 0;
        //定义count数组，用于记录字符串中的字符出现的位置(最多26个小写字母)
        int[] count = new int[26];

        //循环遍历将count中的对应位置字符个数加1
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++;// a 从 0 开始
        }

        //再遍历数组找到可以放到最左侧的字符
        for(int i = 0; i < s.length(); i++){
            //先移动位置，比position大的话，则不移动
            if(s.charAt(position) > s.charAt(i)) position = i;
            //找到第一个减到0的数，此时的position就是最左侧字符
            if(--count[s.charAt(i) - 'a'] == 0) break;
        }
        //递归调用，再寻找最左侧字符
        return s.charAt(position) + removeDuplicateLetters2(s.substring(position + 1).replaceAll(s.charAt(position) + "", "" ));
    }

    /**
     * 方法三：使用栈
     * 时间复杂度：O(n)
     * 在之前我们递归调用的时候我们可以发现，我们每次确定一个可以放置在最左侧的字符，加入确定左侧字符，如果后面出现则剔除字符，再确定最左侧字符。
     * 通过分析，我门能够想到，这是符合栈 “后进先出” 的特点，就可以想到用栈来解决这个问题，这样就可以避开递归了。
     */
     public String removeDuplicateLetters3(String s) {
         //处理特殊情况
         if(s.length() == 0) return "";

         Deque<Character> stack = new ArrayDeque<>();//定义栈来存储最终结果，Java中推荐使用双向队列来定义栈（Stack的封装有问题）

         //定义map来存储字符在字符串中最后出现的位置
         Map<Character, Integer> latestShowUp = new HashMap<>();
         for(int i = 0; i < s.length(); i++){
             latestShowUp.put(s.charAt(i),i);
         }

         //遍历字符串
         for(int i = 0; i < s.length(); i++){
             char c = s.charAt(i);
             if(stack.contains(c)) continue;//栈中已有该字符直接跳过
             while(!stack.isEmpty() && stack.getLast() > c && latestShowUp.get(stack.getLast()) > i){//这里需要循环判断，因为可能多个重复在后面出现
                 stack.removeLast();
             }
             stack.addLast(c);
         }

         //将栈中元素组成字符串返回
         StringBuffer resultBuffer = new StringBuffer();
         int l = stack.size();//坑：这里长度需要拉出来定义，因为在遍历stack过程中，stack一直pop(),stack.size()会一直变小。
         for(int i = 0; i < l; i++){
             resultBuffer.append(stack.pop());
         }

         return resultBuffer.toString();

     }

     //官方题解
     //贪心 + 单调栈
     public String removeDuplicateLettersOfficial(String s) {
         boolean[] vis = new boolean[26];
         int[] num = new int[26];
         for (int i = 0; i < s.length(); i++) {
             num[s.charAt(i) - 'a']++;
         }

         StringBuffer sb = new StringBuffer();
         for (int i = 0; i < s.length(); i++) {
             char ch = s.charAt(i);
             if (!vis[ch - 'a']) {
                 while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                     if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                         vis[sb.charAt(sb.length() - 1) - 'a'] = false;
                         sb.deleteCharAt(sb.length() - 1);
                     } else {
                         break;
                     }
                 }
                 vis[ch - 'a'] = true;
                 sb.append(ch);
             }
             num[ch - 'a'] -= 1;
         }
         return sb.toString();
     }

}

/**
 * 总结：
 * 1.在题意中找出解题所需的基本步骤:
 *   这一题的基本步骤就可以总结为：
 *      每次都去找能确定的最左侧的那个数，从左侧寻找相对较小的那个数，如果这个数前面的数在后面都出现过，则就可以作为最左侧的数，否则，只能原来最左侧的数作为最左侧的数
 *   由此我们可以看出这题每一步都求出当前的最优结果，不考虑后面，我们就能使用贪心策略来解决。
 * 2.善于利用数据结构解决问题：
 *   这一题我们在求解的过程中发现了栈的使用场景，就可以尝试着用栈来解决问题。
 */
